package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * 450. 删除二叉搜索树中的节点
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/8 15:53
 */
public class DeleteNode {

    public static void main(String[] args) {
        DeleteNode test = new DeleteNode();
        TreeNode instance2 = TreeNode.getInstance2();
        TreeNode treeNode = test.deleteNode(instance2, 2);
        System.out.println(treeNode);
    }


    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode f = new TreeNode(0);
        f.left = root;
        TreeNode treeNode = find(f, root, key);
        if (treeNode == null) {
            return root;
        }
        if (treeNode.left != null && treeNode.left.val == key) {
            TreeNode item = treeNode.left;
            TreeNode next;
            if (item.left == null) {
                next = item.right;
            } else {
                TreeNode r = item.right;
                next = find(item, item.left);
                next.right = r;
                if (next.val != item.left.val) {
                    next.left = item.left;
                }
            }
            treeNode.left = next;
        } else {
            TreeNode item = treeNode.right;
            TreeNode next;
            if (item.left == null) {
                next = item.right;
            } else {
                TreeNode r = item.right;
                next = find(item, item.left);
                next.right = r;
                if (next.val != item.left.val) {
                    next.left = item.left;
                }
            }
            treeNode.right = next;
        }
        return f.left;
    }

    private TreeNode find(TreeNode last, TreeNode item, int t) {
        if (item == null) {
            return null;
        }
        int val = item.val;
        if (t == val) {
            return last;
        }
        if (val > t) {
            return find(item, item.left, t);
        } else {
            return find(item, item.right, t);
        }
    }

    private TreeNode find(TreeNode last, TreeNode item) {
        if (item.right == null) {
            last.right = item.left;
            return item;
        }
        return find(item, item.right);
    }

}
